#include <iostream>
#include <vector>

using namespace std;

struct Way {
    int tar, time;
};

const int N = 1010;
vector<vector<Way>> v(N);
int n, m;
int dis[N];
int res = 0x3f3f3f3f;
bool vis[N];

void dfs(int x, int cost) {
    if (x == n) {
        res = cost < res ? cost : res;
        return;
    }

    for (auto w : v[x]) {
        if (!vis[w.tar]) {
            vis[w.tar] = true;
            dfs(w.tar, w.time + (w.tar == n ? 0 : dis[w.tar]) + cost);
            vis[w.tar] = false;
        }
    }
}

int main() {

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> dis[i]; // 输入停留时间

    for (int i = 1; i <= m; ++i) { // 输入城市相连道路和时间
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }

    vis[1] = true;
    dfs(1, 0);
    cout << res << endl;

    return 0;
}